【Leetcode47】Permutations II 全排列 II

发表于 | 分类于

[Leetcode47] Permutations II 全排列 II


“The Linux philosophy is “Laugh in the face of danger”.Oops.Wrong One. “Do it yourself”. Yes, that”s it.”
Linux的哲学就是“在危险面前放声大笑”，呵呵，不是这句，应该是“一切靠自己，自力更生”才对。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 给定一个可包含重复数字的序列，返回所有不重复的全排列。
 * 示例:
 * 输入: [1,1,2]
 * 输出:
 * [
 * [1,1,2],
 * [1,2,1],
 * [2,1,1]
 * ]
 */
public class leetcode47 {
    public List<List<Integer>> permuteUnique (int[] nums) {
        int[] isVisited = new int[nums.length];
        List<List<Integer>> res = new ArrayList<>();
        helper(res, new ArrayList<>(), 0, nums, isVisited);
        Set<List<Integer>> set = new HashSet<>();
        for(List<Integer> list:res)
            set.add(list);
        res = new ArrayList<>();
        res.addAll(set);
        return res;
    }

    public void helper (List<List<Integer>> res, List<Integer> bag, int pos, int[] nums, int[] isVisited) {
        if (pos == nums.length)
            res.add(new ArrayList<>(bag));
        for (int i = 0; i < nums.length; ++i) {
            if (isVisited[i] != 1) {
                bag.add(nums[i]);
                isVisited[i] = 1;
                helper(res, bag, pos + 1, nums, isVisited);
                isVisited[i] = 0;
                bag.remove(bag.size() - 1);
            }
        }
    }

    public static void main (String[] args) {
        int[] nums = new int[]{1, 1, 2};
        new leetcode47().permuteUnique(nums);
    }
}
Thanks!